package com.huawei.tree;

import com.huawei.common.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author admin
 * @Description 113.路径总和II https://leetcode.cn/problems/path-sum-ii/
 * @Date 2023/11/16/22:44
 * @Version 1.0
 */
public class PathSumTwo {

	LinkedList<List<Integer>> res = new LinkedList<>();
	LinkedList<Integer> path = new LinkedList<>();


	/**
	 * 解题思路： 典型的回溯问题，解法包含先序遍历 + 路径记录两部分：
	 * (1) 先序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。
	 * (2) 路径记录： 在先序遍历中，记录从根节点到当前节点的路径。
	 *              当路径满足 (1) 根节点到叶节点形成的路径 且 (2) 各节点值的和等于目标值 targetSum 时，将此路径加入结果列表。
	 * @param root
	 * @param targetSum
	 * @return
	 */
	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
		recur(root, targetSum);
		return res;
	}

	private void recur(TreeNode root, int tar) {
		if (root == null) return;
		path.add(root.val);
		tar -= root.val;
		if (tar == 0 && root.left == null && root.right == null) {
			res.add(new LinkedList<Integer>(path));
		}
		recur(root.left, tar);
		recur(root.right, tar);
		path.removeLast();
	}
}
